package leetcode.editor.cn.dsa14_greedyAlgorithm;
// 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
// 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i
//]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 

import java.util.Arrays;

public class AssignCookies455_1 {
    public static void main(String[] args) {
        Solution solution = new AssignCookies455_1().new Solution();
        int[] g = {2,1,3}, s = {1,1};
        System.out.println(solution.findContentChildren(g, s)); //1
        int[] g2 = {2,1}, s2 = {1,3,2};
        System.out.println(solution.findContentChildren(g2, s2)); //2
        int[] g3 = {1,3,5,7,9}, s3 = {2,4,6,8};
        System.out.println(solution.findContentChildren(g3, s3)); //4
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findContentChildren(int[] g, int[] s) {
            // 对两个数组进行排序
            Arrays.sort(g);
            Arrays.sort(s);
            // 定义两个指针 i 和 j 分别指向数组末位
            int i = g.length - 1, j = s.length - 1;
            int count = 0;
            /**
             * 饼干尺寸s：[2,4,6,8]
             * 孩子胃口g：[1,3,5,7,9]
             * 当孩子胃口 > 饼干尺寸时，饼干不能满足当前孩子胃口，
             *   需要找胃口小的，指针i向前移动
             * 当孩子胃口 <= 饼干尺寸时，当前饼干满足当前孩子胃口，count++
             *   继续遍历下一个饼干，指针j向前移动
             *   继续遍历下一个孩子胃口，指针i向前移动
             */
            while (i >= 0 && j >= 0) { // 任何一个遍历完成则结束
                if (g[i] <= s[j]) {
                    j--;
                    count++;
                }
                i--;
            }
            return count;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}